/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***堆排序    P109                              ***/
/***C++ 实现版本    written by Daniel           ***/
#include <iostream>
#include <ctime>
#include <cstdlib>
using std::cout;
using std::endl;
#define MAX 8000000
void heapSort(int *arr, int size);
void adjustHeap(int *arr, int i, int size);
void printArr(int *arr, int size);

void printArr(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
//红字还是有一点点误区的，顶部肯定要调整，
//但是i = 0的时候是从顶部往底部走的，下面其实部分也需要微微调整
//因为非叶子节点值被交换后并没有和其左右子节点进行比较！！！！
void heapSort(int *arr, int size)
{
    // adjustHeap(arr,1,size);
    // printArr(arr,size);
    // adjustHeap(arr,0,size);
    // printArr(arr,size);
    int temp = 0;
    //对所有的非叶子节点 都执行adjustHeap操作
    for (int i = size / 2 - 1; i >= 0; i--)
    {
        adjustHeap(arr, i, size);
    }
    //
    for (int j = size - 1; j >= 0; j--)
    {
        temp = arr[j];
        arr[j] = arr[0];
        arr[0] = temp;
        adjustHeap(arr, 0, j);
    }
    //printArr(arr, size);
}
/*
作用：将数组按照大顶堆进行调整
参数： arr 数组  i表示非叶子节点在数组中索引
      size 表示要调整的个数，逐渐减少
      //使用的前提是  子树已经是一个大顶堆
返回值：空
*/
void adjustHeap(int *arr, int i, int size)
{
    int temp = arr[i];
    //k=2*i+1 是左子节点,2*i+2是右子节点
    //k<size保证，左子节点一定存在；
    for (int k = 2 * i + 1; k < size; k = 2 * k + 1)
    {
        //k+1<size,保证右子节点存在
        //左子节点 和 右子节点进行比较
        if (k + 1 < size && arr[k] < arr[k + 1])
        {
            //如果右子节点大于左子节点，让k指向右子节点
            k++;
        }
        //让较大的子节点和 父节点的值比较
        if (arr[k] > temp)
        {
            arr[i] = arr[k];
            i = k;
        }
        else
        {
            break;
        }
        arr[i] = temp;
    }
}

int main()
{
    //使用系统时间生成一个随机数种子
    srand(time(NULL));
    int *array = new int[MAX];
    for (int i = 0; i < MAX; i++)
    {
        array[i] = rand() % MAX;
        // cout<<array[i]<<endl;
    }
    time_t now = time(NULL);
    std::cout << "now=" << now << std::endl;
    heapSort(array, MAX);
    printArr(array,MAX);
    time_t newNow = time(NULL);
    std::cout << "newNow=" << newNow << std::endl;
    std::cout << "一共花了" << newNow - now << "秒";
    delete[] array;
    return 0;
}